package my.algo.data;

/**
 * 大顶堆和优先队列
 */
public class PriorityQueue {

    private final int[] data = new int[20];
    private int idx = 0;

    public void enqueue(int value) {
        data[idx++] = value;
        upAdjust();
    }

    private void upAdjust() {
        int childIdx = idx - 1;
        int parentIdx = (childIdx - 1) / 2;
        int temp = data[childIdx];
        while (childIdx > 0 && temp > data[parentIdx]) {
            data[childIdx] = data[parentIdx];
            childIdx = parentIdx;
            parentIdx = (parentIdx - 1) / 2;
        }
        data[childIdx] = temp;
    }

    public int dequeue() {
        if (idx <= 0) {
            throw new IllegalStateException();
        }
        int head = data[0];
        data[0] = data[--idx];
        downAdjust();
        return head;
    }

    private void downAdjust() {
        int parentIdx = 0;
        int temp = data[parentIdx];
        int childIdx = 1;
        while (childIdx < idx) {
            if (childIdx + 1 < idx && data[childIdx + 1] > data[childIdx]) {
                childIdx++;
            }
            if (temp >= data[childIdx]) {
                break;
            }
            data[parentIdx] = data[childIdx];
            parentIdx = childIdx;
            childIdx = 2 * childIdx + 1;
        }
        data[parentIdx] = temp;
    }

    public static void main(String[] args) {
        PriorityQueue queue = new PriorityQueue();
        queue.enqueue(3);
        queue.enqueue(5);
        queue.enqueue(10);
        queue.enqueue(2);
        queue.enqueue(7);
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
    }
}
